package exam.bak.E58;

public class P1 {

    public int weight(int[] weights, int total) {
        int[] dp = new int[total + 1];
        for (int weight : weights) {
            dp[weight] = 1;
        }

        for (int i = 1; i <= total; i++) {
            int min = Integer.MAX_VALUE-1;
            for (int weight : weights) {
                if (i - weight >= 0) {
                    min = Math.min(min, dp[i - weight] + 1);
                }
            }
            dp[i] = min;
        }
        return dp[total] == Integer.MAX_VALUE-1 ? -1 : dp[total];
    }

    public static void main(String[] args) {
        int weight = new P1().weight(new int[]{2}, 3);
        System.out.println(weight);
    }
}
